Many scientific and engineering applications presently involve some sort of digital image processing. The digital images which are studied cover an incredibly broad range of applications including, by way of example, early fetus development using sonograms, astronomical images created through a myriad of light detecting instruments and medical applications such as MRI, PET and NMR devices. In addition, devices as simplistic and pervasive as facsimile machines involve digital images to which the teachings of this invention apply. The processing of these images requires the conversion of a continuous set of analog data into a corresponding digital form. Two-dimensional images are commonly rasterized by scanning images spots contained in the analog data set. Each pixel resulting from the scan is sampled so as to quantize the particular intensity associated with the pixel. These intensity values are combined with the physical coordinates of the pixels to create a representation of the overall image.
Unfortunately, there exist many sources of noise and distortion which degrade the image prior to the time that it is stored. Quantization errors, non-uniform illumination of the image, thermal noise and impulse noise all contribute to inaccuracies which are introduced into the representational image as blurred representations. In order to eliminate these distortions, techniques, falling under the broad category of "deconvolution" methods, have been developed. One such method for deconvolution method well known in the art is the CLEAN technique.
CLEAN was first described by Hogbom in "Aperture Synthesis with a Non-regular Distribution of Interferometer Baselines", Astronomy and Astrophysics Supplement Series, Vol 15, pp. 417-426 (1974). It remains among the most utilized of deconvolution methods in the field of astronomy. The utility of this method has been proven as a result of its ease of programming, accuracy and general applicability to a variety of applications. CLEAN is a nonlinear, arithmetic, sequentially iterative process for achieving deconvolution.
The CLEAN method is further beneficial because it is robust, affords superresolution and does not require precise knowledge of the point spread function (PSF) to achieve acceptable deconvolution. Furthermore, its simple arithmetic approach in the data domain obviates the need for processing involving the inverse domain. As a result, CLEAN has heretofore met the general requirements of most standard deconvolution applications. Additionally, there are a variety of cases in which nonlinear methods, such as CLEAN, present a distinct advantage over linear methods. If the PSF is sparsely sampled, if it drops to zero more than once (such as with a sinc-like function), or if it is asymmetric (as is the case when motion blur is present), linear methods will fail and CLEAN and/or other nonlinear methods may be the only alternative.
One compelling impediment against the use of CLEAN is its computational speed. Like all nonlinear deconvolution schemes, CLEAN is slower (often by an order of magnitude or more) than linear deconvolution. CLEAN has been reported, however, to be faster than many other nonlinear deconvolution methods. See "Comparative Study of Real-Time Deconvolution Methods in Medical Imaging", by N. Cohen and G. Sandri, Biomedical Image Processing and 3-D Microscopy: Proc. SPIE 1660, R. Achyra, C. Cogswell, and D. Goldgof, eds., SPIE, Beliingham, Wash., 1992, pp. 88-94.
Nevertheless, numerous attempts have been made to increase the speed of the CLEAN method. The first known attempt was by Chen and Frater in 1984. See "A High-Speed Hardware `CLEAN` Processor and its use in an Interactive Process", Indirect Imaging, J. Roberts editor, Cambridge University Press, Cambridge, Mass., 1984, pp. 425-430. The speed of CLEAN was significantly improved through the use of a limited instruction set array processor running a radically modified version of CLEAN. The most notable modification in the design of Chen and Frater was the truncation of the PSF ("dirty beam") into a main lobe and sidelobes thereafter partitioning the image. The process was reported to work well, increasing the processing speeds to fractions of a second. Unfortunately, this method, because of such a partitioning scheme precluded applications when the PSF is not sinc-like.
Cohen, in 1992, reported the first real-time CLEAN processor. See "Practical Real-Time Deconvolution and Image Enhancement of Medical Ultrasound", Biomedical Image Processing and 3-D Microscopy: Proc. SPIE 1660, R. Achyra, C. Cogswell, and D. Goldgof, eds., SPIE, Beliingham, Wash., 1992, pp. 72-82. At a 15 Hz rate, 400.times.300 pixel ultrasonic images were deconvolved successfully. Despite these efforts, it has not heretofore been demonstrated that CLEAN or any other deconvolution method, has a general application for more modest computational platforms wherein rapid or real time processing requirements are imposed.
CLEAN is an arithmetic, sequentially iterative process in which each iteration involves the fractional subtraction of the PSF (via loop gain .gamma.) from the data domain at the position of the peak feature within the image or dataset. Each iteration generates as an outcome a component representing the delta function between the PSF and the data domain resulting in an array of CLEAN components. The residual data domain then comprises the data set for the next iteration. When the intensity of the residual data domain falls below a threshold level (T), the subtractive phase terminates. At this point, the above-described array of CLEAN components is available for the next phase of the CLEAN method, the reconstructive phase.
In the reconstructive phase, the array of CLEAN components is multiplied by a second PSF (the "CLEAN beam") to recover the deblurred image. As will be described in detail below, the CLEAN beam is constructed based upon the particular characteristics of the imaging apparatus. Threshold residuals may further be added to the reconstructed image if desired. This would allow random noise to be introduced in the event precision measurements are desired.
One of the drawbacks of the CLEAN method is that during the subtractive stage, considerable time is spent during a large number of iterations searching for data peaks. Thus, CLEAN's search time is large with respect to the time for arithmetic operations, especially for large n-dimensional arrays. The subtractive stage of CLEAN dominates the processing time for deconvolution of the image.
The sequential nature of CLEAN has been believed to be responsible for it success to date. Many investigators of skill in the art have thus believed that any modifications to the CLEAN method which undermine its sequential nature risk degradation of image accuracy.